package Q3;

import java.util.ArrayList;
import java.util.List;

public class Solution {

    public int ret;

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 该数组最长严格上升子序列的长度
     * @param a int整型一维数组 给定的数组
     * @return int整型
     */
    public int LIS (int[] a) {
        // write code here
        int n = a.length;

        dfs(a, n, new ArrayList<>(), 0);

        return ret;
    }

    public void dfs(int[] a, int n, List<Integer> list, int index) {
        if (index == n) {
            int num = Integer.MIN_VALUE;
            for (int i : list) {
                if (i > num) {
                    num = i;
                } else {
                    return;
                }
            }

            ret = Math.max(ret, list.size());
            return;
        }

        for (int i = index; i < n; i++) {
            //选
            list.add(a[i]);
            dfs(a, n, list, i + 1);
            //回溯
            list.remove(list.size() - 1);

            //不选
            dfs(a, n, list, i + 1);
        }
    }
}